#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 724. 寻找数组的中心下标
    // https://leetcode.cn/problems/find-pivot-index/
    int pivotIndex(vector<int>& nums) {
        vector<int> f(nums.size());
        vector<int> g(nums.size());
        
        int n = nums.size() - 1;

        for (int i = 1; i<nums.size(); ++i)
        {
            f[i] = f[i-1] + nums[i-1];
        }
        for (int i = n - 1; i<nums.size(); --i)
        {
            g[i] = g[i+1] + nums[i+1];
        }

        for (int i = 0; i<nums.size(); ++i)
        {
            if (f[i] == g[i])
                return i;
        }

        return -1;
    }

    // 238. 除自身以外数组的乘积
    // https://leetcode.cn/problems/product-of-array-except-self/
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);
        vector<int> ans(n);

        for (int i = 1; i<n; ++i)
            f[i] = f[i-1] * nums[i-1];
        for (int i = n-2; i>=0; --i)
            g[i] = g[i+1] * nums[i+1];
        
        for (int i = 0; i<n; ++i)
            ans[i] = f[i] * g[i];

        return ans;
    }
};